Recently, Davies, Jenssen, Perkins, and Roberts gave a very nice proof of theresult (due, in various parts, to Kahn, Galvin-Tetali, and Zhao) that theindependence polynomial of a $d$-regular graph is maximized by disjoint copiesof $K_{d,d}$. Their proof uses linear programming bounds on the distribution ofa cleverly chosen random variable. In this paper, we use this method to givelower bounds on the independence polynomial of regular graphs. We also give newbounds on the number of independent sets in triangle-free regular graphs.
展开▼
机译：最近，Davies，Jenssen，Perkins和Roberts很好地证明了这一结果（由于不同部分，原因是Kahn，Galvin-Tetali和Zhao），$ d $-正则图的独立多项式被不相交的副本最大化。 $ K_ {d，d} $。他们的证明对聪明选择的随机变量的分布使用线性规划界限。在本文中，我们使用这种方法来给出正则图的独立多项式的下界。我们还为无三角形正则图中的独立集合数赋予了新的界。
展开▼
